package jjn.offer2;

import java.util.Arrays;

/**
 * @author Jiang Jining
 * @since 2023-07-02 13:05
 */
public class Offer2_13 {
    private int[][] sum;
    
    public Offer2_13(int[][] matrix) {
        sum = new int[matrix.length + 1][matrix[0].length + 1];
        for (int i = 0; i < sum.length; i++) {
            sum[i][0] = 0;
        }
        Arrays.fill(sum[0], 0);
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j] - sum[i][j] + matrix[i][j];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sum[row2 + 1][col2 + 1] - sum[row1][col2 + 1]
                - sum[row2 + 1][col1] + sum[row1][col1];
    }
    
    public static void main(String[] args) {
        int[][] matrix = new int[][]{{3, 0, 1, 4, 2}, {5, 6, 3, 2, 1}, {1, 2, 0, 1, 5}, {4, 1, 0, 1, 7}, {1, 0, 3, 0, 5}};
        Offer2_13 offer213 = new Offer2_13(matrix);
        System.out.println("offer213.sumRegion(2,1,4,3) = " + offer213.sumRegion(2, 1, 4, 3));
        System.out.println("offer213.sumRegion(1,1,2,2) = " + offer213.sumRegion(1, 1, 2, 2));
        System.out.println("offer213.sumRegion(1,2,2,4) = " + offer213.sumRegion(1, 2, 2, 4));
        
    }
}
